import org.junit.Test;

import java.util.*;

public class Solution399 {
    /**
     * 给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量，k 是一个浮点型数字。
     * 根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
     * <p>
     * 示例 :
     * 给定 a / b = 2.0, b / c = 3.0
     * 问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
     * 返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]
     */

    private Map<String,Map<String,Double>> graph = new HashMap<>();

    public void buildGraph(List<List<String>> equations, double[] values){
        for (int i = 0; i < values.length; i++) {
            graph.computeIfAbsent(equations.get(i).get(0), k -> new HashMap<>()).put(equations.get(i).get(1), values[i]);
            graph.computeIfAbsent(equations.get(i).get(1), k -> new HashMap<>()).put(equations.get(i).get(0), 1 / values[i]);
        }
    }

    class Pair{
        String key;
        double val;
        public Pair(String key,double val){
            this.key=key;
            this.val=val;
        }
    }

    public double bfs(String a,String b){
        //讲道理,不管a,b是否在graph中,只要想等都应该返回1吧,这里是考虑了0的情况?
        if (!graph.containsKey(a) || !graph.containsKey(b)) {
            return -1.0;
        }
        if (a.equals(b)) {
            return 1.0;
        }
        Queue<Pair> queue=new LinkedList<>();
        queue.add(new Pair(a,1.0));
        HashSet<String> visit=new HashSet<>();
        while(!queue.isEmpty()){
            Pair cur=queue.poll();
            if (!visit.contains(cur.key)) {
                visit.add(cur.key);
                Map<String,Double> map=graph.get(cur.key);
                for (String next:map.keySet()) {
                    if (b.equals(next)) {
                        return cur.val*map.get(next);
                    }
                    queue.add(new Pair(next,cur.val*map.get(next)));
                }
            }
        }
        return -1.0;
    }

    public double dfs(String a,String b,HashSet<String> visit){
        if (!graph.containsKey(a)) {
            return -1;
        }
        if (a.equals(b)) {
            return 1;
        }
        visit.add(a);
        Map<String,Double> nextMap=graph.get(a);
        for (String next:nextMap.keySet()) {
            if (!visit.contains(next)) {
                double subres=dfs(next,b,visit);
                if (subres!=-1) {
                    return subres*nextMap.get(next);
                }
            }
        }
        return -1;
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        buildGraph(equations,values);
        double[] res=new double[queries.size()];
        int index=0;
        for (List<String> query:queries) {
            HashSet<String> visit=new HashSet<>();
            //res[index++]=dfs(query.get(0),query.get(1),visit);
            res[index++]=bfs(query.get(0),query.get(1));
        }
        return res;
    }
}
